/*
 * Programacao concorrente
 * Grupo-03a
 * Brenno Candido					7696500 
 * Jose Victor Uliana Martins		7656620
 * Maria Fernanda Garbim Avelino 	7277562
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>
#include "mpi.h"

#define N 1001 // numero maximo de vertices
#define NTHR 100

// Representa um peso infinito pois o
// maior peso e 100000
const int INF = 1000000;

// Matriz de adjacencia para representar o grafo
int G[N][N];

/*
 * Dado uma Matriz de adjacencia, essa funcao retorna o um vetor
 * com as menores distancias de um vertice de origem passado.
 * Argumentos:
 * 	G: matriz de adjacencia - grafo
 * 	orig: vertice de origem para os menores caminhos
 * 	n: numero de vertices do grafo
 */
int* dijkstra(int G[N][N], int orig, int n) {
	int *visited, *dist; // visited sao os vertices visitados e dist é a menos distancia ate um vetice
	int count, node;
	int i;
	
	// alocacao do vetor de vertices visitados
	visited = (int*)malloc((n+1)*sizeof(int));
	if(!visited) {
		fprintf(stderr, "error during allocation of visited array\n");
		return NULL;
	}
	dist = (int*)malloc((n+1)*sizeof(int));
	if(!dist) {
		fprintf(stderr, "error during allocation of distance array\n");
		return NULL;
	}
	
	// inicializa o vetor visitados com 0 (não visitado) e o vetor
	// de distancia com uma distancia infitita
	for(i=0; i<=n; i++) {
		visited[i] = 0; // marca como nao visitado
		dist[i] = INF; // distancia infinita
	}
	
	dist[orig] = 0; // distancia do vertice origem ate o vertice origem e zero
	node = orig; // no inicial para buscar as menores distancias

	// para todos os vertices
	for(count = n; count>0; count--) {
		
		// busca o node com com menor distancia
		for(i=1; i<=n; i++) {
			// se node nao foi visitado e tem menor distancia que a distancia do node escolhido
			if(!visited[i] && (node == -1 || (dist[i] < dist[node] && dist[i] != 0)))
				node = i;
		}
		visited[node] = 1; // marca como visitado

		// atualiza as distancias do vetor dist para cada vertice
		for(i=1; i<=n; i++) {
			if(dist[i] > dist[node]+G[node][i] && G[node][i] != 0) {
				dist[i] = dist[node]+G[node][i];
			}
		}
		// insere -1 em node para nova busca por melhor node
		node = -1;
	}

	// retorna vetor com as menores distancias a partir do vertice orig
	return dist;
}

/*
 * Retorna o maior valor pertencente ao vetor v de tamanho n
 * Argumentos:
 * 	v: vetor de inteiros
 * 	n: tamanho do vetor v
 */
int max(int* v, int n) {
	int i, max = -1;

	for(i=1; i<=n; i++) {
		if(v[i] > max && v[i] != INF) {
			max = v[i];
		}
	}
	return max;
}

/*
 * Retorna o menor valor pertencente ao vetor v de tamanho n
 * Argumentos:
 * 	v: vetor de inteiros
 * 	n: tamanho do vetor v
 */
int min(int* v, int n) {
	int i, min = INF;

	for(i=1; i<=n; i++) {
		if(v[i] < min) {
			min = v[i];
		}
	}
	return min;
}

int main(int argc, char* argv[]) {
	MPI_Status Stat;
	int lower_bound, upper_bound, partition, rest;
	int n, m, a, b, w, i;
	int rank, size, source;
	int MAX[N];


	MPI_Init(&argc, &argv); // Inicializa a sessao MPI
	MPI_Comm_rank(MPI_COMM_WORLD, &rank); // rank obtem o id do processo
	MPI_Comm_size(MPI_COMM_WORLD, &size); // size obtem o numero de processos

	// se rodar com menos processos do que necessario(2 processos o minimo)
	// encerrar o programa
	if(size < 2) {
		printf("E necessario no minimo 2 processos para rodar esse programa.\n");
		MPI_Finalize();
		return -1;
	}
	
	source = 0; // define processo fonte (mestre)
	if(rank == source) {
		
		// le entrada:
		// n - numero de vertices
		// m - numero de arestas
		scanf(" %d %d", &n, &m);

		// inicializa matriz com 0
		memset(G, 0, sizeof(G[0][0])*n*n);

		// inicializa os pesos dos entre os vertices
		for(i=0; i<=m; i++) {
			scanf(" %d %d %d", &a, &b, &w);
			G[a][b] = w;
			G[b][a] = w;
		}

		// caso exista mais processos do que vertices
		if(size > n)
			size = n+1;

		/*
		 * O processo mestre ira dividir o numero de vertices que devera
		 * se calculado dijkstra nos processos escravos
		 */
		partition = n/(size-1); // particao
		rest = n%(size-1); // resto

		/*
		 * partition e rest serao necessarios para calcular as fronteiras
		 * superiores e inferios da matriz de adjacencia, ou seja, determina
		 * quais são os vertices a serem calculados para cada processo
		 */
		for(i=1; i<size; i++) { // para cada particao...
			/** considera i como numero do processo alvo do mpi_send **/
			// na primeira iteracao
			if(i == 1) {
				lower_bound = 1;
				upper_bound = partition+1;
			}
			else{
				lower_bound	= upper_bound;
				upper_bound = lower_bound+partition;
			}
			// enquando resto for maior que 0, distribui igualmente para cada processo o resto
			if(rest > 0) {
				upper_bound++; // incremente fronteira superior
				rest--; // decremente o resto
			}

			// envia para o processo i os vertices que ele sera responsavel a ser calculados
			MPI_Send(&lower_bound, 1, MPI_INT, i, 1, MPI_COMM_WORLD);
			MPI_Send(&upper_bound, 1, MPI_INT, i, 1, MPI_COMM_WORLD);
		}
	}

	// envia para todos os processos a matriz de adjacencia, size e n pois sera 
	// necessarios cada processo saber esses valores
	MPI_Bcast(G, N*N, MPI_INT, source, MPI_COMM_WORLD);
	MPI_Bcast(&size, 1, MPI_INT, source, MPI_COMM_WORLD);
	MPI_Bcast(&n, 1, MPI_INT, source, MPI_COMM_WORLD);
	
	// se for processo escravo
	if(rank != source && rank < size) {
		// recebe as fronteiras necessarias para saber quias vertices o processo deve calucar
		MPI_Recv(&lower_bound, 1, MPI_INT, source, 1, MPI_COMM_WORLD, &Stat);
		MPI_Recv(&upper_bound, 1, MPI_INT, source, 1, MPI_COMM_WORLD, &Stat);
	

		// inicializa uma regiao paralera com NTHR threads
		/*#pragma omp parallel num_threads(NTHR)
		{
			// cada thread se responsabilizara por calcular um numero de verticas
			#pragma omp for // paraleliza o for*/
				for(i=lower_bound; i<upper_bound; i++) {
					// MAX[i] recebe a maior distancia obitida pelo vetor retornado
					// da funcao dijkstra para o vertice i
					MAX[i] = max(dijkstra(G, i, n), n);
				}
		//}

		// retorna para o proceso source uma parte do vetor MAX com as maiores distancias de cada vertica
		MPI_Send(&lower_bound, 1, MPI_INT, source, 1, MPI_COMM_WORLD);
		MPI_Send(&upper_bound, 1, MPI_INT, source, 1, MPI_COMM_WORLD);
		MPI_Send(&MAX[lower_bound], (upper_bound-lower_bound), MPI_INT, source, 1, MPI_COMM_WORLD);
	}

	if(rank == source) {
		// recebe de cada processo escravo uma parte do vetor MAX
		for(i=1; i<size; i++) {
			MPI_Recv(&lower_bound, 1, MPI_INT, i, 1, MPI_COMM_WORLD, &Stat);
			MPI_Recv(&upper_bound, 1, MPI_INT, i, 1, MPI_COMM_WORLD, &Stat);
			MPI_Recv(&MAX[lower_bound], (upper_bound-lower_bound), MPI_INT, i, 1, MPI_COMM_WORLD, &Stat);
		}
		
		// mostra a menor distancia dentro das menores distancias com a funcao min
		printf("%d\n", min(MAX, n));
	}

	MPI_Finalize(); // finaliza regiao MPI
	return 0;
}
